package prictise.com.application1.suanFa;

import java.util.Stack;

/**
 * 二叉搜索树的第k个结点
 */
public class KNode {
  // 方法二：使用List进行中序遍历二叉搜索树，得到的结果是有序的。因为二叉搜索树是一个有序的数组。
  //
  //①定义一个List集合，将中序遍历的结果添加到List集合中。
  //
  //②注意判断k的时候，要在中序遍历的后面
  
  TreeNode KthNode(TreeNode pRoot, int k) {
    //计数器，记录的是第count小的元素
    int count = 0;
    if (pRoot == null || k <= 0) {
      return null;
    }
    // 定义栈进行存储数据
    Stack<TreeNode> stack = new Stack<>();
    TreeNode node = pRoot;
    // 栈不空，结点不为空
    while (!stack.isEmpty() || node != null) {
      // 如果结点不为空，
      if (node != null) {
        //将当前结点的左子树结点入栈
        stack.push(node);
        //结点继续移动到左边的子结点
        node = node.left;
      } else {
        /**
         当前结点不为空的时候，当点结点出栈，
         判断出栈后的元素是否有右结点，有右节点指向右节点
         结点不为空的话进栈，类似的步骤
         */
        // 出栈弹出的元素，就是按照从小到大的顺序输出的最小值。
        node = stack.pop();
        // 每弹出一个元素，计数器计数一次
        count++;
        // 计数器的大小等于K的时候，返回第k小的元素
        if (count == k) {
          return node;
        }
        node = node.right;
      }
    }
    return null;
  }
  
  class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    
    public TreeNode(int val) {
      this.val = val;
    }
  }
}



